home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / language / isetl.arc / posort.t < prev    next >
Text File  |  1987-08-20  |  1KB  |  55 lines
  1. program top_sort;
  2.     print "Enter a partial order as a set of pairs";
  3.     read po;
  4.     nodes := domain(po) + image(po);
  5.     print ["nodes", nodes];
  6.  
  7.     sort := [];
  8.     while nodes - image(po) /= {} do
  9.     n := arb(nodes - image(po));
  10.     sort := sort with n;
  11.     nodes := nodes less n;
  12.     po{n} := om;
  13.     end;
  14.  
  15.     print ["sort", sort];
  16. end;
  17.  
  18.  
  19. { [1,2], [1,3], [2,4], [2,5], [3,5], [3,6], [4,8], [5,7], [6,7], [7,8] };
  20.  
  21.  
  22.  
  23. $ breadth first (ready is maintained as a queue)
  24. program top_sort;
  25.     print "Enter a partial order as a set of pairs";
  26.     read po;
  27.     nodes := {x: [x,~] in po} + {y: [~,y] in po};
  28.     print ["nodes", nodes];
  29.  
  30.     $ op = inverse of po
  31.     op := { [y,x] : [x,y] in po };
  32.  
  33.     $ count(y) = # predecessors of y
  34.     $ ready    = { y : count(y) = 0 or OM }
  35.     count := { [y, #x] : x=op{y} };
  36.     ready := [ y : y in nodes | count(y) = OM ];
  37.  
  38.     sort := [];
  39.     while ready /= [] do
  40.     take n fromb ready;
  41.     sort := sort with n;
  42.     for y in po{n} do
  43.         count(y) := count(y) - 1;
  44.         if count(y) = 0 then
  45.         ready := ready with y;
  46.         end;
  47.     end;
  48.     end;
  49.  
  50.     print ["sort", sort];
  51. end;
  52.  
  53.  
  54. { [1,2], [1,3], [2,4], [2,5], [3,5], [3,6], [4,8], [5,7], [6,7], [7,8] };
  55.